import org.junit.Test;

import java.lang.reflect.Array;
import java.util.*;

public class Solution436 {
    /**
     * 给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。
     *
     * 对于任何区间，你需要存储的满足条件的区间 j 的最小索引，这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。
     * 如果区间 j 不存在，则将区间 i 存储为 -1。最后，你需要输出一个值为存储的区间值的数组。
     *
     * 注意:
     *
     * 你可以假设区间的终点总是大于它的起始点。
     * 你可以假定这些区间都不具有相同的起始点。
     *
     */
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] temp = new int[n][2];
        for (int i = 0; i < n; i++) {
            temp[i][0] = intervals[i][0];
            temp[i][1] = i;
        }
        Arrays.sort(temp, Comparator.comparingInt(o -> o[0]));
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = binarySearch(temp,0,n - 1,intervals[i][1]);

        }
        return res;
    }
    public int binarySearch(int[][] nums, int left, int right, int target){
        if(left==right) {
            if(nums[left][0]>=target) return nums[left][1];
            if(left+1<nums.length) return nums[left+1][1];
            else return -1;
        }
        int mid=(left+right)/2;
        if(target==nums[mid][0]) return nums[mid][1];
        else if(target<nums[mid][0]) return binarySearch(nums,left,mid-1,target);
        else return binarySearch(nums,mid+1,right,target);
    }

    @Test
    public void test() {
        findRightInterval(new int[][]{{1},{2}});
    }
 }
